package medium;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/9/13 20:04
 */
public class No34_在排序数组中查找元素的第一个和最后一个位置 {
    public static void main(String[] args) {
        Solution34 solution34 = new Solution34();
        int[] nums = new int[]{0, 2, 2, 2, 2, 4, 5, 6, 6, 6, 6, 6, 8};
        int[] res = solution34.searchRange(nums, 222);
        System.out.println(res);

    }
    
}

class Solution34 {
    public int[] searchRange(int[] nums, int target) {
        //二分查找
        int a = 0;
        int b = nums.length - 1;
        int min = searchRangeL(nums, a, b, target);
        int max = searchRangeR(nums, a, b, target);
        return new int[]{min, max};
    }

    public int searchRangeL(int[] nums, int a, int b, int target) {
        //开始查找(左,右)
        int ans = -1;
        while (a <= b) {
            int mid = (a + b) / 2;
            if (nums[mid] > target) {
                b = mid - 1;
            } else if (nums[mid] < target) {
                a = mid + 1;
            } else {
                //主要在这里处理
                //由于这里要求找左边最小的目标索引,故,不能返回!!!
                ans = mid;
                //缩小范围:由于寻找最左边,故要与a接近,故移动b值
                b = mid - 1;
            }
        }
        return ans;
        
    }
    
    public int searchRangeR(int[] nums, int a, int b, int target) {
        //开始查找(左,右)
        int ans = -1;
        while (a <= b) {
            int mid = (a + b) / 2;
            if (nums[mid] > target) {
                b = mid - 1;
            } else if (nums[mid] < target) {
                a = mid + 1;
            } else {
                //主要在这里处理
                //由于这里要求找右边最大的目标索引,故,不能返回!!!
                ans = mid;
                //缩小范围:由于寻找最右边,故要与b接近,故移动a值
                a = mid + 1;
            }
        }
        return ans;
    }
}



    ////第一个位置
    //int min = Integer.MAX_VALUE;
    ////最后一个位置
    //int max = Integer.MIN_VALUE;
    //public int[] searchRange(int[] nums, int target) {
    //    //二分查找
    //    searchRange(nums, 0, nums.length - 1, target);
    //    //如果均不存在,置为-1
    //    if (min == Integer.MAX_VALUE) {
    //        min = -1;
    //    }
    //    if (max == Integer.MIN_VALUE) {
    //        max = -1;
    //    }
    //    return new int[]{min, max};
    //}
    //
    //public void searchRange(int[] nums, int a, int b, int target) {
    //    //递归终止条件
    //    if (a > b) {
    //        return;
    //    }
    //    //通过判断mid位置的值跟target关系决定如何递归
    //    int mid = (a + b) / 2;
    //    if (nums[mid] == target) {
    //        //处理,min,max
    //        min = Math.min(min, mid);
    //        max = Math.max(max, mid);
    //        //一分为二
    //        searchRange(nums, a, mid - 1, target);
    //        searchRange(nums, mid + 1, b, target);
    //    } else if (nums[mid] < target) {
    //        //说明从a-mid位置都比target小,所以target在 (mid+1,b)
    //        searchRange(nums, mid + 1, b, target);
    //    } else {
    //        searchRange(nums, a, mid - 1, target);
    //    } 
    //}



    //public int[] searchRange(int[] nums, int target) {
    //    //暴力法
    //    int red = 0;
    //    int green = nums.length - 1;
    //    //红指针一直走直到遇到跟target一样的值
    //    while (red<nums.length-1 && nums[red] != target) {
    //        //越界问题考虑
    //        red++;
    //    }
    //    //red确定
    //    while (green >= 0 && nums[green] != target) {
    //        //越界问题考虑
    //        green--;
    //    }
    //    //green确定
    //    if (red > green) {
    //        //找不到
    //        return new int[]{-1, -1};
    //    }
    //    return new int[]{red, green};
    //}